/**
 * @file reverse.cpp
 * @author mixinju@outlook.com
 * @brief 两种方法实现单链表的逆转
 * @version 0.1
 * @date 2021-11-20
 *
 * @copyright Copyright (c) 2021
 *
 */

#pragma once
#include "list.h"

/**
 * @brief 使用循环迭代的方法进行逆转
 *
 * @param list
 */
void reverseInIterate(ListNode* list) {
  if (list == nullptr) {
    return;
  }

  ListNode* front = list;
  ListNode* back = nullptr;

  ListNode* temp = nullptr;

  while (front != nullptr) {
    temp = front->next_;  //记录前驱结点的下一个结点
    front->next_ = back;  //把前驱结点的下一个结点赋值为back结点
    back = front;         //更新back结点
    front = temp;         //更新front结点
  }
}

ListNode* reverseInRecursion(ListNode* list) {
  if (list == nullptr || list->next_ == nullptr) {
    return nullptr;
  }

  ListNode* last = reverseInRecursion(list->next_);

  list->next_->next_ = list;
  list->next_ = nullptr;

  return list;
}